package one.linkList;

/**
 * 环形链表 II
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class DetectCycle {
    //时间复杂度：
    //思路：快慢指针，快指针的步数是慢指针步数的2倍。2(l+p) = l+p+k*r;==>l = k*r-p;
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;//慢指针
        ListNode fast = head;//快指针

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                while(head != slow){
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}
